home *** CD-ROM | disk | FTP | other *** search
/ PC-X 1997 October / pcx14_9710.iso / swag / misc.swg / 0191_Pascal code for the Skyline problem.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-11-29  |  11.3 KB  |  296 lines
  1. program skyline_problem;
  2.  
  3. { Programmed by:  Svetlana Kryukova
  4.   Programmed on:  May 19, 1993
  5. }
  6.  
  7. {-------------------------------------------------------------------------}
  8. const 
  9.    MaxR = 20;                 { maximum number of rectangleSkyline }
  10.    MaxSkylineSize = 79;       { 4*MaxR - 1, maximum size of the Skyline }
  11.  
  12. type
  13.    skyline = array [1..MaxSkylineSize] of integer;
  14.    Rectangle = array [1..3] of integer;
  15.    Skylines  = array [1..MaxR] of Rectangle;
  16.    problem_t = record
  17.                 Points : Skylines;
  18.                 size : integer;
  19.              end;
  20.    solution_t = record
  21.                 Points : skyline;
  22.                 size : integer;
  23.              end;
  24.  
  25. {-------------------------------------------------------------------------}
  26. function Base_Case(Buildings: problem_t):boolean;
  27.     { Precondition: Buildings is some problem, such that 
  28.             Buildings.size >= 0 and Buildings.Points is an
  29.             array of buildings presented by the array of their
  30.             coordinates in the form (x1 y1 x2 y2 ... xn) }
  31.     { Postcondition: return value Base_Case is true if and only if
  32.             Buildings is a base-case problem 
  33.             (Buildings.size = 1) }
  34. begin
  35.   Base_Case := (Buildings.size = 1);
  36. end;
  37.  
  38. {-------------------------------------------------------------------------}
  39. procedure Find_Base_Case_Solution(var Buildings: problem_t; 
  40.                   var Skyline : solution_t);
  41.     { Precondition: Buildings is a base-case problem, such that
  42.             Buildings.size = 1 }
  43.     { Postcondition: Skyline is a correct solution to the problem 
  44.             Buildings such that 
  45.             Skyline.Points = Buildings.Points[1] }
  46. var
  47.    i : integer;
  48. begin
  49.   for i := 1 to 3 do
  50.      Skyline.Points[i] := Buildings.Points[1][i];
  51.   Skyline.size := 3;
  52. end;
  53.  
  54. {-------------------------------------------------------------------------}
  55. procedure Split(var Buildings, LeftBuildings, RightBuildings: problem_t);
  56.     { Precondition : Buildings is an array of buildings, presented by
  57.              an array of coordinates.  Building.size > 1
  58.       Postcondition: LeftBuildings and RightBuildings are arrays of 
  59.              buidings and together they are 
  60.              some permutation of the array Buildings and
  61.              |LeftBuildings.size - RightBuildings.size| <= 1 }
  62. var
  63.    i : integer;
  64. begin
  65.  LeftBuildings.size := Buildings.size div 2;
  66.  RightBuildings.size := Buildings.size - Buildings.size div 2; 
  67.     {Assertion :  |LeftBuildings.size - RightBuildings.size| <= 1 }
  68.  
  69.  for i := 1 to LeftBuildings.size do
  70.       LeftBuildings.Points[i] := Buildings.Points[i];
  71.     { Assertion:     for all i such that 1 <= i <= LeftBuildings.size 
  72.             LeftBuildings[i] = Buildings[i] }
  73.  
  74.  for i := LeftBuildings.size + 1 to Buildings.size do
  75.       RightBuildings.Points[i - LeftBuildings.size] := Buildings.Points[i]; 
  76.     { Assertion:     for all i such that 1 <= i <= RightBuildings.size 
  77.             RightBuildings[i] = Buildings[i]+LeftBuildings.size }
  78. end;
  79.    
  80. {-------------------------------------------------------------------------}
  81. procedure Merge(var LeftSkyline, RightSkyline, Skyline : solution_t);
  82.     { Precondition : LeftSkyline and RightSkyline are two arrays of
  83.              coordinates presenting two skyline,
  84.       Postcondition: Skyline is a common skyline for two LeftSkyline
  85.              and RightSkyline }
  86.  
  87. var i,         { pointSkyline to the first unprocessed abscissa of skyline 1 }
  88.     j,         { pointSkyline to the first unprocessed abcsissa of skyline 2 }
  89.     m: integer;
  90.     k : 1..2;
  91.     CurHeightLeftSkyline, CurHeightRightSkyline, CurHeight: integer;
  92.  
  93. begin
  94.   i := 1;
  95.   j := 1;
  96.   Skyline.size := 0;
  97.   CurHeightLeftSkyline := 0;
  98.   CurHeightRightSkyline := 0;
  99.   CurHeight := 0;
  100.   k := 1;
  101.   while (i <= LeftSkyline.size) and (j <= RightSkyline.size) do
  102.       if LeftSkyline.Points[i] < RightSkyline.Points[j] then 
  103.          begin
  104.            if i < LeftSkyline.size then 
  105.             CurHeightLeftSkyline := LeftSkyline.Points[i+1] 
  106.            else CurHeightLeftSkyline := 0;
  107.            if k = 1 then
  108.                if CurHeightLeftSkyline >= CurHeightRightSkyline then
  109.                    begin
  110.                       Skyline.Points[Skyline.size+1] := LeftSkyline.Points[i];
  111.                       Skyline.Points[Skyline.size+2] := CurHeightLeftSkyline;
  112.                       CurHeight := CurHeightLeftSkyline;
  113.                       Skyline.size := Skyline.size + 2;  
  114.                    end
  115.                else
  116.                    begin
  117.                       k := 2;
  118.                       if CurHeightRightSkyline < CurHeight then
  119.                           begin
  120.                               Skyline.Points[Skyline.size+1] :=
  121.                         LeftSkyline.Points[i];
  122.                               Skyline.Points[Skyline.size+2] := 
  123.                         CurHeightRightSkyline;
  124.                               CurHeight := CurHeightRightSkyline;
  125.                               Skyline.size := Skyline.size + 2;
  126.                           end; 
  127.                    end
  128.             else if CurHeightLeftSkyline > CurHeight then
  129.                begin
  130.                  Skyline.Points[Skyline.size+1] := LeftSkyline.Points[i]; 
  131.                  Skyline.Points[Skyline.size+2] := CurHeightLeftSkyline;
  132.                  CurHeight := CurHeightLeftSkyline;
  133.                  k := 1;
  134.                  Skyline.size := Skyline.size + 2;
  135.                end;
  136.            i := i + 2;
  137.          end { if LeftSkyline.Points[i] < RightSkyline.Points[j] }
  138.       else if LeftSkyline.Points[i] > RightSkyline.Points[j] then begin
  139.               if j < RightSkyline.size then 
  140.             CurHeightRightSkyline := RightSkyline.Points[j+1] 
  141.               else CurHeightRightSkyline := 0;
  142.               if k = 2 then 
  143.         if CurHeightRightSkyline >= CurHeightLeftSkyline then begin
  144.                          Skyline.Points[Skyline.size+1] :=
  145.                      RightSkyline.Points[j];
  146.                          Skyline.Points[Skyline.size+2] := 
  147.                      CurHeightRightSkyline;
  148.                          CurHeight := CurHeightRightSkyline;
  149.                          Skyline.size := Skyline.size + 2;  
  150.               end else begin
  151.                          k := 1;
  152.                          if CurHeightLeftSkyline < CurHeight then begin
  153.                               Skyline.Points[Skyline.size+1] :=
  154.                      RightSkyline.Points[j];
  155.                               Skyline.Points[Skyline.size+2] := 
  156.                     CurHeightLeftSkyline;
  157.                               CurHeight := CurHeightLeftSkyline;
  158.                               Skyline.size := Skyline.size + 2;
  159.                          end; 
  160.               end else if CurHeightRightSkyline > CurHeight then begin
  161.                  Skyline.Points[Skyline.size+1] := RightSkyline.Points[j]; 
  162.                  Skyline.Points[Skyline.size+2] := CurHeightRightSkyline;
  163.                  CurHeight := CurHeightRightSkyline;
  164.                  k := 2;
  165.                  Skyline.size := Skyline.size + 2;
  166.           end;
  167.            j := j + 2;
  168.       end { if LeftSkyline.Points[i] > RightSkyline.Points[j] }
  169.            else begin
  170.                 if i < LeftSkyline.size then CurHeightLeftSkyline := 
  171.                     LeftSkyline.Points[i+1] 
  172.                 else CurHeightLeftSkyline := 0;
  173.                 if j < RightSkyline.size then 
  174.             CurHeightRightSkyline := RightSkyline.Points[j+1] 
  175.                 else CurHeightRightSkyline := 0;
  176.                 if CurHeightLeftSkyline >= CurHeightRightSkyline then begin
  177.                      k := 1;
  178.                      if CurHeightLeftSkyline <> CurHeight then begin
  179.                           Skyline.Points[Skyline.size+1] := 
  180.                         LeftSkyline.Points[i];
  181.                           if (i<>LeftSkyline.size) or (j<>RightSkyline.size) 
  182.                             then begin
  183.                 Skyline.Points[Skyline.size+2] := 
  184.                         CurHeightLeftSkyline;
  185.                 Skyline.size := Skyline.size + 1
  186.               end;
  187.                           CurHeight := CurHeightLeftSkyline;
  188.                           Skyline.size := Skyline.size + 1;
  189.                      end;
  190.                 end else begin
  191.                      k := 2;
  192.                      if CurHeightRightSkyline <> CurHeight then begin
  193.                           Skyline.Points[Skyline.size+1] := 
  194.                     RightSkyline.Points[j];
  195.                           Skyline.Points[Skyline.size+2] := 
  196.                     CurHeightRightSkyline;
  197.                           CurHeight := CurHeightRightSkyline;
  198.                           Skyline.size := Skyline.size + 2;
  199.                      end; 
  200.                 end;
  201.               i := i + 2;
  202.               j := j + 2;
  203.          end;
  204.   for m := i to LeftSkyline.size do begin
  205.            Skyline.Points[Skyline.size+1] := LeftSkyline.Points[m]; 
  206.     Skyline.size := Skyline.size + 1;
  207.   end;
  208.   for m := j to RightSkyline.size do begin
  209.            Skyline.Points[Skyline.size+1] := RightSkyline.Points[m]; 
  210.     Skyline.size := Skyline.size + 1; 
  211.   end;
  212. end;
  213.  
  214. {-------------------------------------------------------------------------}
  215. procedure Find_Skyline(var Buildings : problem_t;
  216.                        var Skyline : solution_t);
  217. var
  218.    LeftBuildings, RightBuildings : problem_t;
  219.    LeftSkyline, RightSkyline : solution_t;
  220. begin
  221.  if Base_Case(Buildings) then
  222.      Find_Base_Case_Solution(Buildings, Skyline)
  223.   else 
  224.      begin
  225.        Split(Buildings, LeftBuildings, RightBuildings);
  226.        Find_Skyline(LeftBuildings, LeftSkyline);
  227.        Find_Skyline(RightBuildings, RightSkyline); 
  228.        Merge(LeftSkyline, RightSkyline, Skyline);
  229.      end;
  230. end;
  231.  
  232.  
  233. {-------------------------------------------------------------------------}
  234. procedure GetProblem(var Buildings : problem_t);
  235. var
  236.     i, j : integer;
  237. begin
  238.   write(output, ' Enter the number of buildings in the City: ');
  239.   readln(input, Buildings.size);
  240.   write(output, 
  241.     ' Enter only three coordinates for each building, x1 y x2, ');
  242.   writeln (output, 'representing ');
  243.   writeln (output, '        the building (x1,0),(x1,y),(x2,y) & (x2,0)');
  244.   writeln (output, ' (LIMITATIONS: x in [0..300], y in [0..170])');
  245.   writeln (output);
  246.   for i := 1 to Buildings.size do
  247.      begin
  248.        write(output, ' Enter building#', i:1, ' coordinates: ');
  249.        for j := 1 to 3 do
  250.           read(input, Buildings.Points[i][j]);
  251.      end;
  252. end;
  253.  
  254. {-------------------------------------------------------------------------}
  255. procedure DisplayProblem (var Buildings: problem_t);
  256. var k : integer;
  257. begin
  258.   writeln('==========================================');
  259.   writeln(' Problem is a collection of ', Buildings.size:0, ' builings :');
  260.   for k := 1 to Buildings.size do 
  261.     writeln('      Rectangle #', k:0, ' has coordinates : ', 
  262.         Buildings.Points[k][1]:0, ' ', Buildings.Points[k][2]:0, ' ',
  263.         Buildings.Points[k][3]:0);
  264. end;
  265.  
  266. {-------------------------------------------------------------------------}
  267. procedure DisplaySolution (var Skyline: solution_t);
  268. var k : integer;
  269. begin
  270.   writeln('= = = = = = = = = = = = = = = = = = = = = ');
  271.   writeln(' Solution is a skyline of size ', Skyline.size:0);
  272.   for k := 1 to Skyline.size do 
  273.     if (k mod 2) = 1 then writeln('       x', ((k - 1)div 2 + 1):0, ' = ', 
  274.                         Skyline.Points[k]:0)
  275.     else writeln('       y', ((k-1) div 2 + 1):0, ' = ', Skyline.Points[k]:0);
  276. end;
  277.  
  278.  
  279. {-------------------------------------------------------------------------}
  280. procedure SolveOneProblem;
  281. var
  282.    Buildings : problem_t;
  283.    Skyline : solution_t;
  284. begin
  285.       GetProblem(Buildings);
  286.       DisplayProblem(Buildings); 
  287.       Find_Skyline(Buildings, Skyline);
  288.       DisplaySolution(Skyline);
  289. end;
  290.  
  291. {-------------------------------------------------------------------------}
  292. begin
  293.    SolveOneProblem;
  294. end.
  295.  
  296.